package com.yhq.basic.algorithm.array;

/**
 * @author hqyin
 * @date 2023/8/24 4:55 下午
 */
public class CircleSingleLinked<T> {
    private Node<T> first;
    private Node<T> last;
    private int size;

    public void add(T e) {
        linkLast(e);
    }

    private void linkLast(T e) {
        Node<T> newNode = new Node<>(e, null);
        Node<T> pre = last;
        if (pre == null) {
            first = newNode;
            first.next = newNode;
        } else {
            pre.next = newNode;
        }
        newNode.next = first;
        last = newNode;
        size++;
    }

    public int size() {
        return size;
    }

    public T josephus(int exitCnt) {
        int cnt = 0;
        Node<T> cur = first;
        Node<T> pre = last;
        while (size != 1) {
            if (cnt == exitCnt - 1) {
                Node<T> tmp = cur.next;
                T item = unlink(pre, cur);
                cur = tmp;
                System.out.println("======移除：" + item);
                cnt = 0;
            } else {
                pre = cur;
                cur = cur.next;
                cnt++;
            }

        }
        return cur.item;
    }

    private T unlink(Node<T> pre, Node<T> cur) {
        if(cur == first) {
            first = cur.next;
        }
        pre.next = cur.next;
        cur.next = null;
        T result = cur.item;
        cur.item = null;
        size--;
        return result;
    }

    private static class Node<T> {
        T item;
        Node<T> next;

        public Node(T item, Node<T> next) {
            this.item = item;
            this.next = next;
        }
    }

}
